Міністерство освіти і науки України
НУ “Львівська політехніка”
Кафедра автоматизованих систем управління
Лабораторна робота №3
з дисципліни:
Теорія алгоритмів і математичні основи представлення знань
на тему:
” Емуляція на ПЕОМ багаторегiстрових машин ”
Мета лабораторної роботи - автоматизувати процес доведення рекурсивності (алгоритмiчностi)певних функцій f : N^K -> N i g : E*^k -> E* шляхом емуляції на ПЕОМ N-БРМ i E*-БРМ , що дасть змогу беспосередньо перевiрити правiльнiсть побудови N-БРМ Мf i E*-БРМ М*g, для бiльш глибокого засвоїння прямих методів доведення рекурсивностi функцiй (предикатiв).
I. ЗАГАЛЬНІ ПОЛОЖЕННЯ
Розглянемо математичне визначення [1,2] класів функцій та предикатів, що вважаються точним аналогом інтуїтивного поняття алгоритму (взагалі кажучи, часткового).
1. Введемо зчисленні множини символів або послідовностей символів (слів ,ідентифікаторів і т.п.) із довільної конструктивної множини:
а) індивідні : x,y,z,x0,y0,z0,x1,y1z1, ... xj ,yj,zj, ...;
б) функціональні: f,g,h,f0, g0, h0, f0, g1, h1,...fj, gj, hj,...;
в) предикатні: P,Q,R,P0,Q0,R0,P1,Q1,R0, ... Pj,Qj,Rj, ...;
г) константи: a,b,c,a0,b0,c0,a1,b1,c1, ... aj,bj,cj, ...;
д) мітки: q,i,j,q0,i0,j0,q1,i1,j1, ... qk,ik,jk, ...
Кожному функціональному та предикатному символу U однозначно ставиться у відповідність натуральне число n, яке називається арністю даного символа. Цей символ позначається через U (n) , або U(x1,x2,..,xn)та т.п., і називається n-арним символом. Вважається, що ідеалізований об'єкт – 0 - арний функціональний символ U (n) співпадає з символом константи.
Схемою оператора присвоювання називається вираз виду:
z(i) = f (m) 0(x(1),..,x(m)) . (1)
Схемою оператора пересилки називається вираз виду:
z(k) = y(j) (2)
Схемою присвоювання константи називається вираз виду:
z(k) = a, або z(k) = f j (0) (3)
Схемою умови називається вираз виду:
P (s) (x(1)..x(s)) (4)
Схемою програми (СП) S називатимемо об'єкт виду
q0 Ф[0] (i0,j0)
q1 Ф[1] (i1,j1)
................ (5)
qs Ф[s] (is,js)
В (1) Qs = Qs1 U Qs2, де Qs1 = {q0,q1,..qs}, і
Qs2 = {i0,j0,..,is,js} - підмножини множин міток. Як правило, якщо не вказане уточнення, будемо вважати, що qi ≠ qj, якщо i ≠ j, (qi,qj належать Q1).Мітки із Q1 називаються мітками передачі управління, а мітки із (Qs - Qs1) - кінцевими мітками.
Для всіх k 3є [0 ÷ s], Ф[k] - це одна із схем (1) - (4).
Сукупність всіх індивідних змінних СП (5) називається пам"яттю схеми S. Сукупність константанктних, функціональних, предикатних символів і пам"яті S називається сигнатурою, або базисом, схеми S.
Конструкція вигляду
qr Ф[r] (ir,jr)
із (5) називається схемою команди.
Схемою операторного алгоритму (СОА), або схемою операторної процедури, називається об"єкт виду :
SA = (x1,x2,..,xn; S ;y), (6)
де x1,..,xn,y - змінні, S - СП вигляду (5).
Схемою предикатногоо алгоритму (СПА), або схемою предикатної процедури, називається об"єкт виду :
SP = (x1,x2,..,xn; S ;q[.t.],q[.f.]), (7)
де x1,..,xn, - змінні, S - СП вигляду (5),
а q[.t.],q[.f.]) - кінцеві мітки СП S.
Зауважимо, що пам"яттю алгоритмів (6),(7) називається об"єднання пам"ятті S і змінних x1,..,xn,y, і x1,..,xn називаються вхідними змінними, а y - вихідною змінною .
Ми визначили СП, СОА і СОП як деякі формальні, синтаксичні конструкціє. Яка ж семантика (сенс) цих конструкцій? Як із них отримати справжні алгоритми (програми) ?
Семантика схем задається за допомогою _ інтерпретацій.
Інтерпретація ...
